package a_hashmap;

import java.util.NoSuchElementException;

/**
 * 基于开散列的哈希表实现
 */
public class MyHashMap {

    private class Node {
        int key;
        int value;
        Node next;

        Node(int key, int value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    // 当前哈希表中实际存储元素的个数
    private int size;
    // 默认哈希表的长度
    private static final int DEFAULT_CAPACITY = 16;
    // 默认负载因子
    private static final double LOAD_FACTOR = 0.75;
    // 实际存储 key-value 的数组
    private Node[] data;
    // 哈希运算：取模
    private int M;

    public MyHashMap() {
        this(DEFAULT_CAPACITY);
    }
    public MyHashMap(int initCap) {
        data = new Node[initCap];
        this.M = initCap;
    }

    // 添加操作
    public int put(int key, int value) {
        // 计算索引
        int index = hash(key);
        // 查找是否存在 key
        for(Node node = data[index]; node != null; node = node.next) {
            if(node.key == key) {
                // 说明 key 已存在，那就更新 value 的值
                int oldValue = node.value;
                node.value = value;
                return oldValue;
            }
        }
        // 不存在 key,那就新增
        Node newNode = new Node(key, value, data[index]);
        data[index] = newNode;
        size ++;
        // 判断是否需要扩容
        if(size >= LOAD_FACTOR * data.length) {
            // TODO 扩容
            resize();
        }
        return value;
    }

    // 哈希表扩容
    private void resize() {
        // 建立新的哈希表，长度为原来的二倍
        this.M = M * 2;
        Node[] newData = new Node[M];
        // 遍历原表中的所有 key, 重新插入新表的位置；之前不同的key对应同一个位置，但在新表中不一定位置相同
        for (int i = 0; i < data.length; i++) {
            for (Node j = data[i]; j != null;) {
                int newIndex = hash(j.key);
                // 暂存 j 的后继节点
                Node next = j.next;
                // 将 j 插入 newData 中的 newIndex 处
                j.next = newData[newIndex];
                newData[newIndex] = j;
                // 再搬移原来桶中的下一个节点
                j = next;
            }
        }
        // 结束后，更新引用
        this.data = newData;
    }

    // 删除操作
    public int remove(int key) {
        int index = hash(key);
        // 查找是否存在 key
        Node prev = data[index];
        // 先看看是不是头节点
        if(prev.key == key) {
            // 删除 prev
            int val = prev.value;
            data[index] = prev.next;
            prev.next = prev = null;
            size --;
            return val;
        }
        while(prev.next != null) {
            if(prev.next.key == key) {
                // 删除 prev 的后继节点
                Node node = prev.next;
                int val = node.value;
                prev.next = node.next;
                node.next = node = null;
                size --;
                return val;
            }
            prev = prev.next;
        }
        // 不存在 key
        throw new NoSuchElementException("没有该 key 值！");
    }

    // 查找操作
    public int get(int key) {
        int index = hash(key);
        for(Node x = data[index]; x != null; x = x.next) {
            if(x.key == key) {
                return x.value;
            }
        }
        throw new NoSuchElementException("没有该 key 值！");
    }
    public boolean containsKey(int key) {
        int index = hash(key);
        for(Node x = data[index]; x != null; x = x.next) {
            if(x.key == key) {
                return true;
            }
        }
        return false;
    }
    public boolean containsValue(int value) {
        // 因为无法通过 value 值计算出key值，所以只能遍历全表查询
        // 先遍历每个桶的位置
        for (int i = 0; i < data.length; i++) {
            // 再遍历每个桶中的 value 值
            for (Node j = data[i]; j != null; j = j.next) {
                if(j.value == value) {
                    return true;
                }
            }
        }
        return false;
    }

    // 哈希函数
    private int hash(int key) {
        return Math.abs(key) % M;
    }
}
